上篇連結:樹的定義與追蹤

引線樹

n個樹葉中，會產生n+1個多餘的NULL空間浪費，因此建立有用的引線。  

規則

以中序追蹤建立陣列

引線節點左邊接中序左空間，右邊接中序右空間

無連接之引線向上根結點接(下圖範例先以999表示)

表示法與追蹤

在結構左右分別建立儲存TF的空間，T為引線，F為小孩

threaded_pointer insucc(threaded_pointer tree){
  threaded_pointer temp;
  temp = tree->right_child;
  if (!tree->right_thread)
    while (!temp->left_thread) 
      temp = temp->left_child;
  return temp;
}

void tinorder(threaded_pointer tree){
   /*引線二元樹 之中序追蹤  */
    threaded_pointer temp = tree;
    for ( ; ; ) {
        temp = insucc(temp);            
        if (temp==tree) break;
        printf(“%3c”, temp->data);
    }
}

插入及演算法

要求：插入一新節點成為節點 parent 的右小孩(right child )

1. 右子樹為空:
   
2. 右子樹不為空:
   
   【資料結構】引線的練習實作

堆積樹

規則

最大樹:樹的每個節點都不小於其子樹。

最小樹:樹的每個節點都不大於其子樹。

最大堆積樹/最小堆疊樹:為最大最小樹的完全二元樹。

時間複雜度

插入及演算法

void insert_max_heap(element item, int *n){
  int i;
  if (HEAP_FULL(*n)) {
    fprintf(stderr, “堆積已滿\n”);
    exit(1);
  } 
  i = ++(*n);
  while ((i != 1) && (item.key > heap[i/2].key)){heap[i] = heap[i/2];}
  heap[i]= item;
}

刪除及演算法

【資料結構】堆積樹(陣列法) 未完成

二元搜尋樹

說明

• 1.根結點中的兩邊固定一邊大另一邊小。
• 2.下方節點當作新的根結點，繼續符合一邊大一邊小的規則。
• 3.無重複值。
• 4.二元搜尋樹是進行搜尋、插入、刪除最好的資料結構。
  

範例

實作:二元搜尋樹的建立、搜尋、插入、刪除
【資料結構】二元搜尋樹:添加節點
【資料結構】二元搜尋樹:刪除節點

待補